#include <stdio.h>
#include <stdlib.h>

// 基数排序可以用链表结构，也可以用稳定的计数排序方法，按位重复排序

typedef struct Node{
    int data;
    struct Node *next;
    
} Node;

// 创建节点
Node* createNode(int data) {
    Node* newnode = (Node*)malloc(sizeof(Node));  // 动态分配内存
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}

void addnode(Node** head,int data){
    if(*head == NULL){
        *head = createNode(data);
    }else{
        Node* temp = *head;
        while (temp->next!=NULL){
            temp = temp->next;
        }
        Node* newnode = createNode(data);
        temp->next = newnode; 
    }
}

void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

void radixSort(int arr[],int n){
    int max = arr[0];
    for(int i = 0;i<n;i++){
        if(arr[i]>max){
            max = arr[i];
        }
    }
    Node* buckets[10] = {NULL};
    for(int exp = 1;max>exp;exp*=10){
        printf("exp = %d  loading...\n",exp);
        for(int i=0;i<n;i++){
            addnode(&buckets[(arr[i]/exp)%10],arr[i]);
        }
        int idx = 0;
        for(int i=0;i<10;i++){
            Node* node = buckets[i];
            while (node!=NULL)
            {
                arr[idx] = node->data;
                idx++;
                node = node->next;
            }
            
            freeList(buckets[i]);
            buckets[i] = NULL;
        }
    }
}

int main(){
    int arr[] = {218,224,391,443,22,337,1125,49,506};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    radixSort(arr,n);
    
    for(int i=0;i<n;i++){printf("%d ",arr[i]);}

    return 0;
}